package com.剑指offer;

import java.util.ArrayList;

/*
 * 小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,
 * 他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟
 * 有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他
 * 就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把
 * 问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
 * */
public class _41和为S的连续正数序列
{
    public static void main(String[] args)
    {
        ArrayList<ArrayList<Integer>> arrayLists = FindContinuousSequence(1000000);
        System.out.println(arrayLists);
    }

    public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum)
    {
        ArrayList<ArrayList<Integer>> finalList = new ArrayList<>();
        ArrayList<Integer> list = new ArrayList<>();
        int temp1 = 0;
        int temp2 = 0;
        while (true)
        {
            while (true)
            {
                if (sum(list) > sum)
                {
                    break;
                }
                if (sum(list) == sum)
                {
                    finalList.add(new ArrayList<>(list));
                    break;
                }
                list.add(temp1);
                temp1++;
            }
            temp2++;
            temp1 = temp2;
            list.clear();
            if (temp2 > sum / 2)
            {
                break;
            }
        }
        return finalList;

    }

    public static int sum(ArrayList<Integer> list)
    {
        int temp = 0;
        for (int i = 0; i < list.size(); i++)
        {
            temp += list.get(i);
        }
        return temp;
    }

}
